﻿#pragma once
#include "Index.h"
/**
 * 外观数列
 * https://leetcode.cn/problems/count-and-say/
 * 字符串
 *
 * 给定一个正整数 n ，输出外观数列的第 n 项。
 *「外观数列」是一个整数序列，从数字 1 开始，序列中的每一项都是对前一项的描述。
 * 你可以将其视作是由递归公式定义的数字字符串序列：
 * countAndSay(1) = "1"
 * countAndSay(n) 是对 countAndSay(n-1) 的描述，然后转换成另一个数字字符串。
 */
class CountAndSay
{
public:
    std::string countAndSay(int n)
    {
        if (n <= 0)
            return "";

        std::string desc = "1";
        for (int i = 2; i <= n; ++i)
        {
            if (_memoMap.count(i))
                desc = _memoMap[i];
            else
            {
                std::string newDesc;
                const int descSize = desc.size();
                int sta = 0, fin = 0;
                while (sta < descSize)
                {
                    while (fin < descSize && desc[sta] == desc[fin])
                        fin++;
                    newDesc += std::to_string(fin - sta) + desc[sta];
                    sta = fin;
                }
                desc = newDesc;
                _memoMap[i] = desc;
            }
        }
        return desc;
    }
private:
    static std::map<int, std::string> _memoMap;
};
std::map<int, std::string> CountAndSay::_memoMap;


#ifdef DEV_TEST
#include <gtest/gtest.h>
TEST(CountAndSayTest, countAndSay)
{
    CountAndSay s;
    ASSERT_EQ(s.countAndSay(1), "1");
    ASSERT_EQ(s.countAndSay(2), "11");
    ASSERT_EQ(s.countAndSay(3), "21");
    ASSERT_EQ(s.countAndSay(4), "1211");
    ASSERT_EQ(s.countAndSay(5), "111221");
    ASSERT_EQ(s.countAndSay(6), "312211");
    ASSERT_EQ(s.countAndSay(7), "13112221");
}
#endif